COMMENT ⊗   VALID 00005 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.S Basic Research in Artificial Intelligence and Formal Reasoning
C00010 00003		2. Non-monotonic reasoning.
C00017 00004		3. Introspection in logic programming.
C00024 00005	PROPOSED WORK
C00035 ENDMK
C⊗;
.S Basic Research in Artificial Intelligence and Formal Reasoning

FIX PERSONNEL
//pers John#McCarthy, Richard#Weyhrauch, Lewis#Creary, Luigia#Aiello, 
Jussi#Ketonen, Ma#Xiwen Jon#Doyle sra Christopher#Goad, Carolyn#Talcott,
Ben#Moszkowski

Applied research requires basic research to replenish the stock of ideas
on which its progress depends.
The long range goals of work in basic AI and formal reasoning are 
to make computers carry out the
reasoning required to solve problems.
Our work over the past few years has made it considerably clearer how our
formal approach can be applied to AI and MTC problems.
This brings application nearer, especially in the area of mathematical
theory of computation.



.ss Formal Reasoning
John McCarthy continued his work in formalization
of the common sense facts about the world needed for intelligent
behavior and also work in formalization of computer programs.

	McCarthy's personal research concerns the formalization of
common sense knowledge and common sense reasoning
in mathematical logical languages.  Such
formalization is required to represent
the information in the memory of a computer and to make programs
that can reason with the information in order to solve problems.
It is now widely agreed (e.g. including Newell, Nilsson and Minsky)
 that progress in artificial intelligence
is limited by our ability to express common sense knowledge and
reasoning.  There isn't widespread agreement on how to do this,
and McCarthy's work explores one end of the spectrum of ideas -
using mathematical logic.

	Since 1981, McCarthy made substantial progress on three
problems:

	1. Formalization of knowledge about knowledge.  Knowledge
The importance of representing knowledge about knowledge is discussed
elsewhere in this proposal and our previous proposals.  In particular,
the proposed "intelligence analyst" requires knowledge about
knowledge.

	McCarthy
developed a first order language that admits Kripke style possible
worlds as objects and use the Kripke accessibility relation to
formalize knowledge of a person of the value of an expression.
McCarthy showed how to use this formalism to express the facts of
a difficult mathematical puzzle involving knowledge - the following puzzle
of Mr. S and Mr. P.

	Two numbers are chosen between 2 and 99 inclusive.  Mr. P
is told the product and Mr. S is told the sum.  The following
dialog occurs:

Mr. P: I don't know the numbers.

Mr. S: I knew you didn't know them.  I don't know them either.

Mr. P: Now I know the numbers.

Mr. S: Now I know the numbers.

Problem: What are the numbers?

Answer: The numbers are 4 and 13.

	The key difficulty to formalizing Mr. S and Mr. P comes from
the need to represent ignorance.  How do we represent the fact that
all Mr. S initially knows about the numbers is given by his knowledge
of the sum and all he knows about Mr. P's knowledge is that Mr.
P knows the product?  Representation of this ignorance is accomplished
by asserting the existence of a sufficiently comprehensive collection
of possible worlds accessible to Mr. S.  Using the possible worlds
in the language itself rather than regarding them as metalinguistic
devices has been uncongenial to logicians.  However, none of the experts on
modal logic to whom the problem has been submitted were able to
formulate it directly in modal logic.

	This example problem attracted our attention to an issue that
is fundamental to all programs that reason about knowledge - the
representation of ignorance.  Thus in the ANALYST problem, the program
may conjecture that all the Russians should know about a certain
radar is what can be deduced from its appearance, where it is used,
and the articles in Aviation Week.  We can express this by saying
that any plausible conjecture compatible with this information is
a possibility for them.  If they behave so as to rule out such a
possibility, then we conjecture that they have an additional source
of information.  The explicitly Kripkean formalization developed
in connection with Mr. S and Mr. P should work here as well.

	McCarthy's formalization of Mr. S and Mr. P was modified
by Ma Xiwen, a Chinese visitor, and used for an FOL proof that
transformed the problem into a purely arithmetic problem.  Unfortunately,
McCarthy found an error in Ma's axioms, and it isn't clear that
when the error is fixed, the proof still works.  Also the axioms
describing the effect of learning, e.g. what happens when Mr. P
learns that Mr. S knew he didn't know the numbers, seem to have
some defects.  Formalizing the effect of learning that other people
know something (or don't) is required for making the Analyst program
work or for any program with similar capabilities.

	2. Non-monotonic reasoning.

	In 1980 McCarthy published "Circumscription: a method
of non-monotonic reasoning".  Since that time circumscription
has been further developed.  A forthcoming paper will describe
a new formalization and many new applications.

	There seem to be many kinds of non-monotonic reasoning
formalizable by circumscription, and it isn't clear how to unify
them.  It also isn't clear whether circumscription is a universal
form of non-monotonic reasoning or whether others will be required.
It is known to subsume many examples given earlier by McDermott and
Doyle and by Reiter, and there are no outstanding cases where it
is not known how to do it.

	Here are some example uses of circumscription.

1. As a communication convention.  Suppose  A  tells  B  about
a situation involving a bird.  If the bird may not be able to fly, and this
is relevant to solving the problem, then  A  should mention
the relevant information.  Whereas if the bird can fly, there is
no requirement to mention the fact.

2. As a database or information storage convention.  It can be a
convention of a particular database that certain predicates have
their minimal extension.  This generalizes the closed world
assumption of Reiter.  When a database makes the closed world assumption
for all predicates it is reasonable to imbed this fact in the
programs that use the database.
However, when there
is a priority structure among the predicates, we need to express
the priorities as sentences of the database, perhaps included
in a preamble to it.

Neither 1 nor 2 requires that most birds can fly.
Should it happen that most birds that are subject to the communication
or about which information is requested from the data base cannot fly, the
convention may lead to inefficiency but not incorrectness.

3. As a rule of conjecture.  This use was emphasized
in (McCarthy 1980).  The circumscriptions may be regarded as expressions of some
probabilistic notions such as "most birds can fly" or they may be
expressions of simple cases.  Thus it is simple to conjecture that
there are no relevant present
material objects other
than those whose presence can be inferred.  It is also
a simple conjecture that a tool asserted to be present is usable
for its normal function.  Such conjecture sometimes conflict, but there
is nothing wrong with having incompatible conjectures on hand.  Besides
the possibility of deciding that one is correct and the other wrong, it
is possible to use one for generating possible exceptions to the other.

4. As a representation of a policy.  The example is Doyle's "The meeting
will be on Wednesday unless another decision is explicitly made".

5. As a very streamlined expression of probabilistic information when
numerical probabilities, especially conditional probabilities, are
unobtainable.  Since circumscription doesn't provide numerical probabilities,
its probabilistic interpetation involves
probabilities that are either infinitesimal, within an
infinitesimal of one, or intermediate - without any discrimination
among the intermediate values.  The circumscriptions give conditional
probabilities.  Thus we may treat the probability that a bird
can't fly as an infinitesimal.  However, if the rare
event occurs that the bird is a penguin, then the conditional probability that
it can fly is infinitesimal, but we may hear of some rare condition
that would allow it to fly after all.

	Why don't we use finite
probabilities combined by the usual laws?  That would be fine
if we had the numbers, but circumscription is usable when we can't
get the numbers or find their use inconvenient.  Note that the
general probability that a bird can fly may be irrelevant, because
we are interested in particular situations which weigh in favor or
against a particular bird flying.

	Notice that circumscription does not provide for
weighing evidence; it is appropriate
when the information permits snap decisions.  However, many
cases nominally treated in terms of weighing information are in fact
cases in which the weights are such that circumscription and other
defaults work better.
	3. Introspection in logic programming.

	In the early 1970s Alain Colmerauer of Mareilles University
in France and Robert Kowalski of Imperial College in London proposed
the use of first order logic as a programming language, and the Marseilles
group subsequently embodied these ideas in a programming language called
Prolog.  Prolog has become popular in Europe for artificial intelligence
use, and the Japanese "Fifth Generation" project proposes to use
logic programming.  Of people who have used both LISP and Prolog,
some prefer one and some the other.  Alan Robinson and others have
tried to develop languages that allow both styles of programming.
McCarthy has tried Prolog and still prefers LISP.

	However, certain issues of programming style come up more
clearly in Prolog than in LISP.  One of these can be called
"introspection", wherein a program uses itself and its memory
state as data.  This is similar to the "reflection" studied by
Brian Smith in his well known Harvard PhD thesis.

	Kowalski proposed a slogan "Algorithm = logic + control",
and proposed that Prolog permitted a neat separation.  McCarthy
has investigated this claim using a map coloring logic program
devised by Luis Pereira and Antonio Porto of the University of
Lisbon in Portugal.  He noted that two efficient algorithms
for map coloring could be regarded as having the same logic
as the original Pereira-Porto logic program but more sophisticated
control.

	One of these algorithms involved a "postponement heuristic"
that re-ordered goals to put last goals that could still be realized
regardless of how the previous goals were achieved.  In the map
coloring case, after some goals have been postponed, still others
become postponable, and this process can be repeated.

	The second algorithm uses so-called Kempe transformations
to modify assignments already made to variables when the algorithm
gets stuck.  It is far superior to backtracking for map coloring,
but it can still be described as control applied to the original
Pereira-Porto logic.  However, this kind of control requires that
the program, when stuck, go into an "introspective mode" wherein
it looks at data structures created by the interpreter that are
not ordinarily accessible to the program itself.  This is the
work whose ideas overlap those of Brian Smith.  Smith applied them
to LISP, but has recently been exploring the idea that they are
even more applicable to a logic programming language such as
Prolog.

	The two kinds of introspection can be called syntactic
and semantic.  The postponement heuristic is syntactic in that
it involves looking at the goals and re-ordering them before
attempting to realize any of them.  The Kempe heuristic is
semantic in that it doesn't re-order the goals, but modifies
the order in which alternatives are tried in a task dependent
manner and requires that the program look at its own stack
of tasks.

	McCarthy's results show that in this case the Kowalski
doctrine can be maintained in the map coloring case.  Both algorithms
can be regarded as sophisticated control applied to simple logic.
The connrol mechanisms required in the two cases go far beyond
what the logic programmers, e.g. Keith Clark, Pereira and Porto,
and Herve Gallaire, had been willing to contemplate.  While they
have some generality, it seems likely that additional problems
will require additional mechansism.

	So far it hasn't proved especially convenient to program
by beginning with a simple logic and adding a sophisticated control.
However, such techniques should make it easier to prove the
correctness of programs.  Further exploration of the Kowalski
doctrine applied to logic programming may turn up interesting
and useful methods of control and other heuristics.

	(McCarthy 1982) "Coloring Maps and the Kowalski Doctrine"
presents some of these ideas.
PROPOSED WORK

	McCarthy will continue his work on formalizing common sense
reasoning during the period of the proposal.  The following will be
emphasized.

	1. Inventory of common sense representation, common sense knowledge
and common sense reasoning human capabilities.

	There is widespread agreement that lack of general common
sense knowledge is the key present limitation on the applicability of
AI programs.  However, each of the authors making this point 
(e.g. Newell, Nilsson, Minsky,
Genesereth and McCarthy) has had to content himself
with giving examples.  The time seems to be ripe to attempt a comprehensive
list.  McCarthy will prepare a paper giving such a list during 1983
and plans to use this paper as a basis for discussion with other
AI researchers.  It is extremely unlikely that the initial list
will be accepted as comprehensive, and we plan further editions over
the three year period of the contract.  In so far as our list is
comprehensive, individual AI researchers can concentrate their attention
on specific aspects of common sense knowledge or reasoning.

	2. Formalization of additional common sense concepts.  A
key problem that has been around for many years is that of formalizing
the consequences of actions in when concurrent events are taking
place.  There are some new ideas, and Yoram Moses is exploring
writing a thesis in this area.  So far as I know, no existing AI programs
can handle this at all.

	The simple blocks world formalisms have long suffered from
the "frame problem" of specifying what doesn't change when an action
takes place.  McCarthy has developed a formalization using circumscription
that avoids requiring that the description of an action describe
what doesn't change.  He will try to elaborate this into a general
solution of the frame problem.


	3. Non-monotonic reasoning.  Circumscription has mathematical
properties related to the notion of satisfaction in mathematical logic.
McCarthy has shown (unpublished) that in the propositional case, determining
the models resulting from circumscribing a formula leads to a tree
of satisfaction problems.  The useful case of predicate circumscription
should lead to a generalization of the satisfaction problem.  Progress
probably depends on attracting the attention of mathematical logicians
to the problem.  Yoram Moses has started on some aspects of it.

	McCarthy has identified two important properties of the human intellect
that have not been put in computer programs.  We call them ambiguity
tolerance and elaboration tolerance, and they can both be treated by
circumscription.  (Ambiguity tolerance was mentioned vaguely by Dreyfuss
in his book "What Computers Can't Do" as something that computers
can't do).

	"Ambiguity tolerance" refers to the fact that humans successfully
use concepts that are subsequently shown to be ambiguous.  Even after
the ambiguity is understood a person uses the ambiguous form of the
concept in situations in which the ambiguity doesn't show up.
If all concepts used by AI programs were required to be unambiguous, it
would mean that all possible philosophy would have to be done before
any AI.  Therefore, AI programs must use ambiguous concepts.  It seems
that circumscription or other non-monotonic reasoning can be used to
allow the inference that a concept is unambiguous in a particular
instance.

	Elaboration tolerance is a similar phenomenon.  We can use
a representation in which the location of a university
 or even a building is considered independent of the situation.  Nevertheless,
if it is necessary to consider elaborating the representation in order
to consider moving the institution, this can be done.  Again circumscription
can be used to make this capability available to programs.

3. Identifying intellectual mechanisms.

	Besides those based on non-monotonic reasoning, human intelligence
embodies many mechanisms not yet incorporated in formal systems.  McCarthy
has uncovered some of these, and plans to study them.
Here are examples:

a. Common Business Communication Language

	McCarthy (1982) explores the requirements for business communication
between programs belonging to different organizations.  For example, a
purchasing program belonging to one company might inquire about price
and delivery of some product and place an order.  Similarly a program
belonging to one military organization might inquire about the readiness
of airplanes or the availability of certain spare parts.  With a suitable
authorization, it might issue a requisition.  When this problem was first
considered, it was supposed that it was just a grubby standardization
problem, but further examination shows that it involves formalizing
the semantics (not syntax) of a substantial and interesting
 fragment of natural language.  The present languages used for
communication between AI programs and their users are inadequate
to express the concepts required.  The internal languages so far used
in AI are also inadequate.

b. Modifying programs without reading them

	Modifying the behavior of a computer program usually requires
a detailed study of the relevant part of the program and the data
structures it uses.  Much less is required in communicating with
a human.  For example, the head of an airline might tell his subordinates
that that Zoroastrian passengers should receive a complementary drink
if they fly on Zoroaster's birthday.  He does not have to mention
or even know how records are kept - whether in the head of ticket
agent for a very small airline, in ledgers for an old fashioned
airline, or in a computer.  The reason he can do this is that
he is allowed to refer to external events - not just inputs -
in expressing his wishes.  McCarthy has noticed that with suitable
programming languages computers can also be instructed without
understanding their internal workings.  The Elephant language,
developed by McCarthy, obviates the need to mention many data
structures, because the user can refer to past events without
referring to any data structure for rememembering past events.
We plan to explore these possibilities further.


c. Reification.

	Human thought and language often makes nouns of verbs
and adjectives.  Examples: think → thought, red → redness,
to attack → attack.  Philosophers call this "to reify" i.e.
"to make a thing out of" from the Latin word "re" meaning "thing".
They have mainly been concerned with cases in which reification
leads to error.

	However, reification seems to be an important intellectual
process and AI programs will have to do it.  Example: "How many
things are still wrong with the boat now that you have fixed some
of them?"  We plan to study reification and to formalize some
AI examples in which it is useful.